#ifndef EXP__CIRCULAR_LIST_HPP
#define EXP__CIRCULAR_LIST_HPP
#include <iostream>

namespace my_data
{
/**
 * @brief Node结构体
 */ 
struct Node{
  Node(const int &val = 0, Node *p = nullptr)
    :data(val),next(p){}
  int data;
  Node* next;    
};
typedef Node * ptrToNode;

/**
 * @brief 循环链表类
 */ 
class CircularList
{
public:
    CircularList();
    ~CircularList();
    int length;

/**
 * @brief 判断是否为空
 */ 
  inline bool empty();
/**
 * @brief 在头部插入一个node
 */
  void push_front(const int& val);
/**
 * @brief 在尾部插入一个node
 */
  void push_back(const int& val);
/**
 * @brief 弹出头部一个node
 */
  int pop_front();
/**
 * @brief 得到pos上的指针
 */ 
  ptrToNode get_element(const int& pos);
/**
 * @brief 清空链表
 */ 
  void clear();
/**
 * @brief 移除指定位置的node
 */ 
  int remove(const int& pos);
/**
 * @brief 打印输出
 */ 
  void print();

private:
    ptrToNode head; // 头指针
    ptrToNode rear; // 尾指针
};

CircularList::CircularList()
:length(0)
{
  head = new Node(0);
  head->next = head;
  rear = NULL;
}

CircularList::~CircularList()
{
  if(head != NULL)
  {
    ptrToNode tmp_node = head->next;
    //从head->next开始删，直到head->next == rear
    while(tmp_node != rear && tmp_node != head)
    {
      head->next = tmp_node->next;
      delete tmp_node;
      tmp_node = head->next;
    }
    //只剩下head和rear没删
    delete head;
    head = NULL;
    delete rear;
    rear = NULL;
  }
}

inline bool CircularList::empty()
{
  return (length==0);
}


void CircularList::push_front(const int& val)
{
  //空表
  if(this->empty())
  {
    //只有一个结点的时候rear->next = NULL,并不会让它指向自己
    ptrToNode new_node = new Node(val, head);
    head->next = new_node;
    rear = new_node;
  }
  else
  // 头插法
  {
    ptrToNode new_node = new Node(val, head->next);
    // 将新节点放在head->next
    rear->next = new_node;
    head->next = new_node;
  }
  this->length++;
}

void CircularList::push_back(const int& val)
{
  if(this->empty())
  {
    ptrToNode new_node = new Node(val, head);
    head->next = new_node;
    rear = new_node;
  }
  else
  // 尾插法
  {
    ptrToNode new_node = new Node(val, head->next);
    // 新节点为尾部
    rear->next = new_node;
    rear = new_node;
  }
  ++length;
}

int CircularList::pop_front()
{
  // 链表为空，报错
  if(this->empty())
  {
    throw "list is empty";
    return -1;
  }
  // 获取第一个节点
  ptrToNode start = head->next;
  int ret = start->data;
  // 如果只有一个节点，初始化头、尾指针
  if(length == 1)
  {
    delete start;
    head->next = head;
    rear = NULL;
  }
  else
  {
    ptrToNode tmp_node = start->next;
    head->next = tmp_node;
    rear->next = tmp_node;
    delete start;
  }
  --length;
  return ret;
}

ptrToNode CircularList::get_element(const int& pos)
{
  if(pos<0 || pos>=length || this->empty())
  {
    return NULL;
  }
  else
  {
    ptrToNode node = head->next;
    for(int i = 0;i<pos;++i)
    {
      node=node->next;
    }
    return node;
  }
}

void CircularList::clear()
{
  ptrToNode tmp_node = head->next;
  while(tmp_node != rear)
  {
    head->next = tmp_node->next;
    delete tmp_node;
    tmp_node = head->next;
  }
  head->next = NULL;
  delete rear;
  rear = NULL;
  length = 0;
}


int CircularList::remove(const int& pos)
{
  // 链表为空或者节点不存在，报错
  if(pos<0 || pos>=length || this->empty())
  {
    throw "remove error";
    return -1;
  }
  // 得到第一个节点
  ptrToNode node = head->next;
  int ret;
  // 链表长度为1
  if(length == 1)
  {
    ret = node->data;
    delete node;
    head->next = head;
    rear=NULL;
  }
  else
  {
    // 如果删除的是第一个节点
    if(pos == 0)
    {
      ptrToNode p = node->next;
      head->next = p;
      rear->next = p;
      ret = node->data;
      delete node;
    }
    else
    {
      // 寻找对应位置
      for(int i=0;i<pos-1;++i)
      {
        node=node->next;
      }
      // 删除的是队尾
      if(pos == length-1)
      {
        ret = rear->data;
        delete rear;
        rear = node;
        node->next=head->next;
      }
      // 删除的既不是尾也不是头
      else
      {
        ptrToNode tmp = node->next;
        node->next = tmp->next;
        ret = tmp->data;
        delete tmp;
        tmp = NULL;
      }
    }
  }
  --length;
  return ret;
}

void CircularList::print()
{
  std::cout<<"Print List:"<<std::endl;
  if(!empty())
  {
    ptrToNode p = head->next;
    while(p)
    {
      std::cout<<p->data<<" ";
      p = p->next;
      if(p==head->next)
      {
        break;
      }
    }
  }
  std::cout<<std::endl;
}

}//namespace my_data



#endif  //EXP__CIRCULAR_LIST_HPP